package com.shuzijun.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class PermutationsIi{
    public static void main(String[] args) {
         
         Solution solution = new PermutationsIi().new Solution();
        
        
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        private ArrayList<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        HashMap<Integer, Integer> hm = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int count = 1;
            if (hm.containsKey(nums[i])){
                count += hm.get(nums[i]);
            }
            hm.put(nums[i],count );
        }

        int n = hm.size();
        int[] uniqueNums = new int[n];
        int[] counts = new int[n];
        int k = 0;
        for (int i = 0; i < nums.length; i++) {
            if (hm.containsKey(nums[i])){
                uniqueNums[k] = nums[i];
                counts[k] = hm.get(nums[i]);
                k++;
                hm.remove(nums[i]);
            }
        }
        backTrack(uniqueNums,counts,0,new ArrayList<>(),nums.length);
        return result;
    }

        private void backTrack(int[] uniqueNums, int[] counts, int k, ArrayList<Object> path, int n) {
            if (k == n){
                result.add(new ArrayList(path));
                return;
            }

            for (int i = 0; i < uniqueNums.length; i++) {
                if (counts[i] == 0)continue;

                path.add(uniqueNums[i]);
                counts[i]--;

                backTrack(uniqueNums,counts,k+1,path,n);
                path.remove(path.size()-1);
                counts[i]++;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}